package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/minimum-size-subarray-sum/description/?envType=study-plan-v2&envId=top-interview-150">长度最小的子数组(Minimum Size Subarray Sum)</a>
 * <p>给定一个含有 n 个正整数的数组和一个正整数 target 。</p>
 * <p>找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：target = 7, nums = [2,3,1,2,4,3]
 *      输出：2
 *      解释：子数组 [4,3] 是该条件下的长度最小的子数组。
 *
 * 示例 2：
 *      输入：target = 4, nums = [1,4,4]
 *      输出：1
 *
 * 示例 3：
 *      输入：target = 11, nums = [1,1,1,1,1,1,1,1]
 *      输出：0
 * </pre>
 * </p>
 *
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>1 <= target <= 10^9</li>
 *         <li>1 <= nums.length <= 10^5</li>
 *         <li>1 <= nums[i] <= 10^5</li>
 *     </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/10/25 13:22
 */
public class LC0209MinimumSizeSubarraySum_M {

    static class Solution {
        public int minSubArrayLen(int target, int[] nums) {
            int len = nums.length;
            if (len == 0) {
                return 0;
            }
            int ret = Integer.MAX_VALUE;
            int start = 0;
            int end = 0;
            int sum = 0;
            while (end < len) {
                sum += nums[end];
                while (sum >= target) {
                    ret = Math.min(ret, end - start + 1);
                    sum -= nums[start];
                    start++;
                }
                end++;
            }
            return ret == Integer.MAX_VALUE ? 0 : ret;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.minSubArrayLen(7, new int[]{2, 3, 1, 2, 4, 3}));
        System.out.println(solution.minSubArrayLen(4, new int[]{1, 4, 4}));
        System.out.println(solution.minSubArrayLen(11, new int[]{1, 1, 1, 1, 1, 1, 1, 1}));
    }
}
